<!DOCTYPE html>
<html lang="en">
  <head>
    <meta charset="UTF-8" />
    <meta name="viewport" content="width=device-width, initial-scale=1.0" />
    <title>插入排序</title>
  </head>
  <body>
    <script>
      // 插入排序算法步骤：
      // 1.从第一个元素开始，该元素可以认为已经被排序
      // 2.取出下一个元素，在已经排序的元素序列中从后向前扫描
      // 3.如果该元素（已排序）大于新元素，将该元素移到下一位置
      // 4.重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
      // 5.将新元素插入到该位置后
      // 6.重复步骤2~5
      
      // for循环版本
      function insertSort(arr) {
        let length = arr.length;
        let temp, index;
        debugger;
        for (let i = 1; i < length; i++) {
          debugger;
          temp = arr[i];
          for (let j = i - 1; j >= 0; j--) {
            if (temp < arr[j]) {
              index = j;
              arr[j + 1] = arr[j];
            }
            console.log(arr)
          }
          arr[index] = temp;
        }
        return arr;
      }
      console.log(insertSort([5, 4, 3, 2, 1]));

      // while版本:
      function insertSortWhile(arr) {
        let length = arr.length;
        let temp;
        for (let i = 1; i < length; i++) {
          temp = arr[i];
          let j = i;
          while (j > 0 && temp < arr[j - 1]) {
            arr[j] = arr[j - 1];
            j--;
          }
          arr[j] = temp;

          console.log(arr);
        }
        return arr;
      }
      // console.log(insertSortWhile([5, 4, 3, 2, 1]));
    </script>
  </body>
</html>
